package a4_dichteste_ecke;

import a1_graph_lib.AIGraphCounter;

public class Dichtste_Ecke {

	private final static int MAX_INT = Integer.MAX_VALUE;
	private final static String KOSTEN = "0";
	private final static String VORGEANGER = "vorgeanger";
	private final static String NACHFOLGER = "nachfolger";
	private static final String NAME = "NAME";
	
	/**
	 * Die Suche eines guenstigen kreises ueber die Dichteste Ecke in Einem Vollstaendigem Graphen
	 * @param graph Der Vollstaendige Graph
	 * @return Der Graph mit eingeragenem Kreis unter "vorgeanger" und "nachfolger".
	 */
	public static AIGraphCounter guenstiegenKreisFinden(AIGraphCounter graph){
		
		//Setzen und Initalisiren des Start Vertices
		int startVertice = graph.getVertices().get(0);
		setVertice(graph, startVertice, startVertice, startVertice);
		
		System.out.println("Starte Mit der Ecke: " + startVertice + ", der Name ist: " + getVerticeName(graph, startVertice) + "\n");
		
		//Dichteste Ecken Bestimmen ueber die Kanten
		SortetEdges sortet_kanten = new SortetEdges(graph);

		//Solange es noch Kanten giebt
		for(int i = 1; i < graph.getVertices().size(); i++){
			
			//Dichteste Ecke Finden
			int vertice_id = getDichtesteEcke(graph, sortet_kanten);
				
			//Variablen fuer die Positionirung intialisiren
			int nextVertice = getNachfolger(graph ,startVertice);
			int beste_position = 1;
			int beste_kosten = MAX_INT;
				
			//Durchprobieren aller Positionen
			for(int k = 1; k <= i; k++){

				//Kosten holen Giebt auch den Aktuellen stand der Dinge aus
				int temp_kosten = getKostenif(graph, startVertice, vertice_id, k);
					
				//kosten Vergleichen und Gegebenfals beste_position updaten
				if(beste_kosten > temp_kosten){
					beste_kosten = temp_kosten;
					beste_position = k;
				}
			
				//Variable fuer den naechsten durchgang vorbereiten
				nextVertice = getNachfolger(graph ,nextVertice);
			}
				
			//Beste Gefundene Position setzten
			setNewVertice(graph, startVertice, vertice_id, beste_position);
			//Lediglich zur ausgabe des Aktuellen Kreises
			getAktKosten(graph, startVertice);
			
		}
		//Graph zuruckgeben
	return graph;	
	}		
	
	/**
	 * Giebt eine dichteste ecke zurueck und wenn es keine giebt -1
	 * @param graph Der Graph
	 * @param sortet_kanten Die Sortirten Kanten : SortetEdges
	 * @return Die id Der derichtesten Ecke oder -1
	 */
	private static int getDichtesteEcke(AIGraphCounter graph, SortetEdges sortet_kanten) {
		
		//Dichteste Ecken zurucksetzen
		sortet_kanten.resetIndex();
		
		//Id des Vertex initalisieren um dies suche zu Starten
		int vertice_id =  -1;
		int edge = -1;
		
		//Solange die guenstigsten kante durchgehen bis eine gefunden wurde die zu einer dichtesten Ecke gehoert
		while( vertice_id < 0 && (!sortet_kanten.isEmpty())){
			edge = sortet_kanten.getGuenstigste();
			vertice_id = getTheNewVertice(graph, edge);
		}
	
		//Dichteste Ecken zurucksetzen
		sortet_kanten.resetIndex();
		
		System.out.println(	"Naechste dichteste Ecke Gefunden die ID ist: " + vertice_id + ", der Name ist: " + 
							getVerticeName(graph, vertice_id) + ", Die Kosten der Edge sind: " + getKostenEdge(graph, edge));
		
		return vertice_id;
	}

	/**
	 * Fuegt einen Vertice in den Kreis ein
	 * @param graph Der Graph
	 * @param startVertice Der Startvertice
	 * @param vertice_id Der eizufuegende Vertice
	 * @param position Die Position an der ein einzufuegen ist
	 */
	private static void setNewVertice(AIGraphCounter graph, int startVertice, int vertice_id, int position) {

		for(int i = 1; i < position; i++){
			startVertice = getNachfolger(graph, startVertice);
		}
		
		int nachfolger = getNachfolger(graph, startVertice);
		
		setVertice(graph, vertice_id, startVertice, nachfolger);
	}

	/**
	 * Setzt die Vor und Nachfoger um einen Vertex
	 * @param graph Der Graph
	 * @param vertice Der Vertice
	 * @param vorgeanger Der Vorgaenger
	 * @param nachfolger Der Nachfolger
	 */
	private static void setVertice(AIGraphCounter graph, int vertice, int vorgeanger, int nachfolger) {
		setNachfolger(graph, vorgeanger, vertice);
		setVorgeanger(graph, vertice, vorgeanger);
		setNachfolger(graph, vertice, nachfolger);
		setVorgeanger(graph, nachfolger, vertice);
	}
	
	/**
	 * Finder Im kontext des Graphen einen Vertex zu einer Kante
	 * @param graph Der Graph
	 * @param edge Die ID der Edge
	 * @return Die ID des Vertex oder -1 wenn Die Kante nicht die beiden Mengen schneidet
	 */
	private static int getTheNewVertice(AIGraphCounter graph, int edge) {

		if(getVorgeanger(graph, graph.getTarget(edge)) == MAX_INT){
			if(getVorgeanger(graph, graph.getSource(edge)) != MAX_INT){
				return graph.getTarget(edge);
			}
		} else {
			if(getVorgeanger(graph, graph.getSource(edge)) == MAX_INT){
				return graph.getSource(edge);
			}
		}
		return -1;
	}
	
	/**
	 * Gibt die kosten zurueck wenn man einen vertex an einer bestimeten stelle einfuegen wuerde
	 * @param graph	Der Graph
	 * @param startVertice Der Startvertice
	 * @param vertice_id Die ID Der Zu testenen Vertex
	 * @param position Die zu Testende Position
	 * @return Die Kosten wenn man den wertex an der Stelle einfuegen wuerde
	 */
	private static int getKostenif(AIGraphCounter graph, int startVertice, int vertice_id, int position) {

		int aktVertice = startVertice;
		int nextVertice = getNachfolger(graph ,startVertice);
		int akt_position = 1;
		int kosten = 0;
		
		while(akt_position == 1 || aktVertice != startVertice){
			
			if(akt_position == position){
				kosten = kosten + getKostenEdge(graph, aktVertice, vertice_id);
				kosten = kosten + getKostenEdge(graph, vertice_id, nextVertice);
			} else {
				kosten = kosten + getKostenEdge(graph, aktVertice, nextVertice);
			}
			
			akt_position = akt_position + 1;
			aktVertice = nextVertice;
			nextVertice = getNachfolger(graph ,nextVertice);
		}
		
		System.out.println("Kosten Pruefung fuer Position: " +  position + ", mit den Kosten: " + kosten);
		
		return kosten;
	}
	
	/**
	 * Giebt die kosten de Aktuellen Kreise zurueck
	 * @param graph Der Graph
	 * @param startVertice Der Startvertice
	 * @return Die Kosten des Kreises
	 */
	public static int getAktKosten(AIGraphCounter graph, int startVertice) {
		
		int aktVertice = startVertice;
		int nextVertice = getNachfolger(graph ,startVertice);
		boolean first_position = true;
		int kosten = 0;
		
		while(first_position || aktVertice != startVertice){
		
			int edge = getEdgeID(graph, aktVertice, nextVertice);
			
			System.out.println(	"Kante von Vertice ID: " + aktVertice + ", mit Namen: " + getVerticeName(graph, aktVertice) +
								", zu Vertice ID: " + nextVertice + ", mit Namen: " + getVerticeName(graph, nextVertice) +
								" , an der Edge ID: " + edge + ", mit den Kosten: " + getKostenEdge(graph, edge));
			
			kosten = kosten + getKostenEdge(graph, aktVertice, nextVertice);
			first_position = false;
			aktVertice = nextVertice;
			nextVertice = getNachfolger(graph ,nextVertice);
		}
	
		System.out.println("Die Gesamtkosten sind: " + kosten + "\n");
		return kosten;
	}
	
	/**
	 * Sucht die ID iner egde duch zwei Vertex
	 * @param graph Der Graph
	 * @param startVertice Der StartVertex der Edge
	 * @param endVertice Der EndVertex der Edge
	 * @return Die ID der Ege oder -1 Wen es keine Passende giebt
	 */
	private static int getEdgeID(AIGraphCounter graph, int startVertice, int endVertice){
		
		for(int edge : graph.getIncident(startVertice)){
			if(graph.getSource(edge) == startVertice){
				if(graph.getTarget(edge) == endVertice){
					return edge;
				}
			} else if(graph.getSource(edge) == endVertice){
				if(graph.getTarget(edge) == startVertice){
					return edge;
				}
			}
		}
		
		return -1;
	}
	
	/**
	 * Gibt die kosten einer Edge zuruck die zwischen zwei knoten liegt
	 * @param graph Der Graph
	 * @param startVertice Der StartVertex der Edge
	 * @param endVertice Der EndVertex der Edge
	 * @return Die Kosten oder null wenn beide Vertex der Selbe sind oder eine Exeption wenn es keine kante zweischen den beiden giebt
	 * @pre Der Graph muss Vollstaendig sein
	 */
	private static int getKostenEdge(AIGraphCounter graph, int startVertice, int endVertice) {

		int edge = getEdgeID(graph, startVertice, endVertice);

		if(startVertice == endVertice){
			return 0;
		}
		
		if(edge < 0){
			throw new IllegalArgumentException(	"Es giebt keine kante zwischen den Vertex: " + getVerticeName(graph, startVertice) +
												" : " + getVerticeName(graph, endVertice));
		}
		
		return getKostenEdge(graph, edge);
	}
	
	private static int getKostenEdge(AIGraphCounter graph, int edge) {
		return graph.getValE(edge, KOSTEN);
	}
	
	private static void setVorgeanger(AIGraphCounter graph, int vertice, int vorgeanger) {
		graph.setValV(vertice, VORGEANGER, vorgeanger);
	}

	private static void setNachfolger(AIGraphCounter graph, int vertice, int nachfolger) {
		graph.setValV(vertice, NACHFOLGER, nachfolger);
	}
	
	private static int getVorgeanger(AIGraphCounter graph, int vertice) {
		return graph.getValV(vertice, VORGEANGER);
	}
	private static int getNachfolger(AIGraphCounter graph, int vertice) {
		return graph.getValV(vertice, NACHFOLGER);
	}

	private static String getVerticeName(AIGraphCounter graph, int vertex) {
		return graph.getStrV(vertex, NAME);
	}

}

